package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/9/8 17:41
 * @Description:二叉搜索树转换为排序双向循环链表
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */

public class Num36_Tree2DoubleLinkedList {
    // 该题目的关键有两点
    // 1.ADT的中序遍历结果就是从小到大的升序结果
    // 2.node.right => 链表的next指针，node.left => 链表的prev指针
    public TreeNode treeToDoublyList(TreeNode root) {
        // 若空树返回空；只有根节点的树，直接返回根节点
        if (root == null)
            return null;
        if (root.left == null && root.right == null)
            return root;
        // 先递归处理左子树
        // 此时左子树已经是一个排序好的双向链表，left指向链表头，需要找到链表尾部与root连接
        TreeNode left = treeToDoublyList(root.left);
        TreeNode leftTail = left;
        while (leftTail != null && leftTail.right != null)
            leftTail = leftTail.right;
        // 此时leftTail指向左树链表尾部,将leftTail与根节点连接
        if (left != null) {
            leftTail.right = root;
            root.left = leftTail;
        }
        // 再递归处理右子树
        TreeNode right = treeToDoublyList(root.right);
        // 此时右子树已经是一个排序好的双向链表，right指向链表头，找到右侧子树的尾部，与左侧链表头相连
        TreeNode rightTail = right;
        while (rightTail != null && rightTail.right != null)
            rightTail = rightTail.right;
        // 连接根节点与右侧链表头
        if (right != null) {
            right.left = root;
            root.right = right;
        }
        // 连接整个链表头尾指针，循环链表
        // 左右都不为空
        if (left != null && rightTail != null) {
            left.left = rightTail;
            rightTail.right = left;
            return left;
        }
        // 左空，右不空
        if (left == null && rightTail != null) {
            root.left = rightTail;
            rightTail.right = root;
            return root;
        }
        // 左不空，右空
        left.left = root;
        root.right = left;
        return left;
    }
}
